package wili.misc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import wili.c.Ca;
import wili.c.Misc9a;

/**
 * 自然数递增枚举器（指定进位数制） 可用以帮助取排列数。
 *
 * @author weilai 2022年01月11日
 */
public class CarryBitIterator3 implements Iterator<int[]> {
	/*
	    使用ExprExhauster_test时，它比CarryBitIterator2快几十倍！
	 */
	/**
	 * 可选集。用Object代替下标，适用范围更广，可满足对重复元素的回避。
	 */
	private Object[][] optsList;

	/**
	 * 当前下标集
	 */
	private int[] curInds;

	private Map<Object, Integer> valueToIndMap;

	private List<Object> curValues = new ArrayList<>();

	private int times;

	public void reset() {
		hasNext = null;
		times = 0;
		curInds = null;
		if (valueToIndMap != null)
			valueToIndMap.clear();
	}

	private CarryBitIterator3() {
	}

	public static <T> CarryBitIterator3 newInst(List<List<T>> list) {
		Object[][] aa = new Object[list.size()][];
		for (int i = 0; i < aa.length; i++) {
			aa[i] = list.get(i).toArray();
		}
		CarryBitIterator3 obj = new CarryBitIterator3().init(false, aa);
		return obj;
	}

	public CarryBitIterator3(boolean repeatable, int length, int min, int max) {
		Integer[][] opts = new Integer[length][];
		for (int i = 0; i < opts.length; i++) {
			int[] ints = Misc9a.newInts(min, max, 1);
			opts[i] = Misc9a.intObjsOfInts(ints);
		}
		this.init(repeatable, opts);
	}

	private CarryBitIterator3 init(boolean repeatable, Object[][] opts) {
		if (repeatable) {
			valueToIndMap = null;
		} else {
			valueToIndMap = new HashMap<>();
		}
		this.optsList = opts.clone();
		return this;
	}

	/**
	 * @param repeatable 可重复取值 param optsList optsList[i]指第i个数的可选值 param firstInds
	 *                   初始的可选值下标。
	 */
	public CarryBitIterator3(boolean repeatable, int[]... opts) {
		Object[][] ret = Misc9a.intObjsOfInts2D(opts);
		init(repeatable, ret);
	}

	public CarryBitIterator3(boolean repeatable, double[]... opts) {
		Object[][] ret = Misc9a.numObjsOfInts2D(opts);
		init(repeatable, ret);
	}

	/**
	 *
	 */
	private Boolean hasNext;

	@Override
	public boolean hasNext() {
		if (hasNext != null)
			return hasNext;
		hasNext = (next() != null);
		return hasNext;
	}

	@Override
	public int[] next() {
		int[] ret = next00();
		return ret;
	}

	private void removeFromMap(Object value) {
		if (valueToIndMap == null)
			return;
		if (++inc == 4)
			Ca.pause();
		//System.out.println("\t" + inc + valueToIndMap + ", remove:" + opt);
		valueToIndMap.remove(value);
	}

	private Integer putToMap(Object value, int ind) {
		if (valueToIndMap == null)
			return null;
		if (++inc == 12)
			Ca.pause();
		//System.out.println("\t" + inc + valueToIndMap + ", put:" + opt + "~>" + ind);
		Integer ret = this.valueToIndMap.put(value, ind);
		this.curValues.set(ind, value);
		return ret;
	}

	private int[] next00() {
		if (this.hasNext != null) {
			if (!hasNext)
				return null;
			hasNext = null;
			return curInds;
		}
		if (times == 0) {
			curInds = new int[optsList.length];
			curValues.clear();
			curValues.addAll(Arrays.asList(new Object[curInds.length]));
			if (valueToIndMap == null) {
				for (int i = curInds.length - 1; i >= 0; i--) {
					curValues.set(i, optsList[i][curInds[i]]);
				}
			} else {
				for (int i = 0; i < curInds.length; i++) {
					Object opt;
					curValues.set(i, opt = optsList[i][curInds[i]]);
					int ind = 0;
					while (ind < optsList[i].length && valueToIndMap.containsKey(opt)) {
						if (++ind >= optsList[i].length) {
							hasNext = false;
							Ca.asert(false, "More option value needed.");
							return null;
						}
						curValues.set(i, opt = optsList[i][curInds[i] = ind]);
					}
					putToMap(opt, i);
				}
			}
			++times;
			return this.curInds;
		}
		f1: for (int i = this.optsList.length - 1; i >= 0; i--) {
			Object[] opts = optsList[i];
			int rowInd = this.curInds[i];
			Object preOpt = opts[rowInd];
			Integer preInd = valueToIndMap == null ? null : valueToIndMap.get(preOpt);
			int inc2 = +inc;
			if (inc2 == 23)
				Ca.pause();
			if (preInd != null && preInd >= i)
				removeFromMap(preOpt);
			if (rowInd + 1 >= opts.length) {
				continue;//需要进位。
			} else {
				//依靠自然数自增原理，避免重复元素时，仅需考虑左侧位上各选项。
				Integer vInd = null;
				Object opt = opts[rowInd + 1];
				++this.curInds[i];
				if (valueToIndMap != null) {
					vInd = valueToIndMap.get(opt);
					if (vInd == null) {
					} else if (vInd < i) {
						i++;
						continue;//与左侧冲突，本位自增
					}
				}
				vInd = putToMap(opt, i);
				f2: for (int j = i + 1; j < optsList.length; j++) {
					Object[] optsJ = optsList[j];
					if (valueToIndMap == null) {
						this.curInds[j] = 0;
						curValues.set(j, optsJ[0]);
						continue;
					} else {
						int ind = -1;
						preInd = null;
						while (++ind < optsJ.length) {
							this.curInds[j] = ind;
							preInd = valueToIndMap.get(optsJ[ind]);
							if (preInd == null) {
								curValues.set(j, optsJ[ind]);
								putToMap(optsJ[ind], j);
								continue f2;
							} else {
								if (preInd < j) {
									continue;//与左侧冲突，本位自增
								} else {
									Ca.asert(false, "never?");//进位前信息都从valueToIndMap删除了,故不可能。
									putToMap(optsJ[ind], j);
									continue f2;
								}
							}
						}
						Ca.asert(false, "never.");
						continue f1;//因冲突无值可增时，跳转至最近的冲突位寻求进位。
					}
				}
				++this.times;
				hasNext = null;
				return curInds;
			}
		}
		hasNext = false;
		return null;
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		int ind = -1;
		sb.append("curInds=" + Arrays.toString(curInds));
		for (Object[] aa : optsList) {
			++ind;
			sb.append("\n " + ind + ": " + Arrays.toString(aa));
		}
		return sb.toString();
	}

	@Override
	public void remove() {
	}

	static class Item {
		boolean repeatable;

		public int len, min, max, expectNum;

		public String toString() {
			return len + ":" + min + "~" + max;
		}

		public Item(boolean repeatable, int len, int min, int max, int expectNum) {
			this.repeatable = repeatable;
			this.len = len;
			this.min = min;
			this.max = max;
			this.expectNum = expectNum;
		}
	}

	public static void test() {
		test_newInst();
		int opt = 1;
		//opt = 3;
		if (opt == 1) {
			Item[] test = { new Item(true, 4, 0, 3, 256), //可重复取数
					new Item(false, 4, 0, 3, 24), //不可重复取数
					//====================================
					new Item(false, 2, 10, 20, 110) };
			for (int i = 0; i < test.length; i++) {
				Item item = test[i];
				System.out.println(i + "------" + Arrays.toString(test));
				Iterator<int[]> ca;
				if ("".isEmpty()) {
					ca = new CarryBitIterator3(item.repeatable, item.len, item.min, item.max);
				} else {
					ca = null;//CarryBitIterator2.newInst(item.repeatable, item.len, item.min, item.max);
				}
				int times = 0;
				while (ca.hasNext()) {
					++times;
					int[] nn = ca.next();
					System.out.println(times + ":" + Arrays.toString(nn));
				}
				if (item.expectNum >= 0) {
					Ca.asert(item.expectNum == times, "times=" + times);
				}
				break;
			}
		} else if (opt == 2) {
			test_newInst();
		} else if (opt == 3) {
		}
	}

	static void test_newInst() {
		List<List<Object>> list = new ArrayList<>();
		list.add(Arrays.asList("aa", "bb"));
		list.add(Arrays.asList("11", "22", "33"));
		CarryBitIterator3 obj = CarryBitIterator3.newInst(list);
		List<int[]> indsList = new ArrayList<>();
		int ind = 0;
		while (obj.hasNext()) {
			++ind;
			int[] inds = obj.next();
			Ca.log(ind + ", " + Arrays.toString(inds));
			indsList.add(inds);
		}
		Ca.asert(indsList.size() == 6, ind);
		int[] inds2 = indsList.get(indsList.size() - 1);
		Ca.asert(Arrays.equals(inds2, new int[] { 1, 2 }), "");
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		try {
			test();
		} catch (Throwable e) {
			e.printStackTrace();
		} finally {
			long cost = System.currentTimeMillis() - start;
			System.out.println("Cost:" + cost);
		}
	}

	static int inc;
}
